package com.chj.leetcode.tijie250to300;

public class Code265_PaintHouseII {
	public int minCostII(int[][] costs) {
		int n = costs.length;
		if (n == 0) {
			return 0;
		}

		int K = costs[0].length;
		if (K == 1) {
			return costs[0][0];
		}
		int[][] f = new int[n + 1][K];
		int i, j;
		int min1, min2;
		int id1 = 0;
		int id2 = 0;

		for (i = 0; i < K; i++) {
			f[0][i] = 0;
		}

		for (i = 1; i <= n; i++) {
			min1 = Integer.MAX_VALUE;
			min2 = Integer.MAX_VALUE;

			for (j = 0; j < K; j++) {
				if (f[i - 1][j] < min1) {
					min2 = min1;
					id2 = id1;
					min1 = f[i - 1][j];
					id1 = j;

				} else if (f[i - 1][j] < min2) {
					min2 = f[i - 1][j];
					id2 = j;
				}
			}

			for (j = 0; j < K; j++) {
				f[i][j] = costs[i - 1][j];
				if (j != id1) {
					f[i][j] += min1;

				} else if (j != id2) {
					f[i][j] += min2;
				}
			}
		}

		int res = Integer.MAX_VALUE;
		for (i = 0; i < K; i++) {
			res = Math.min(res, f[n][i]);
		}
		return res;

	}

	public int minCost02(int[][] costs) {
		int n = costs.length;
		if (n == 0) {
			return 0;
		}

		int K = costs[0].length;
		if (K == 1) {
			return costs[0][0];
		}

		int[][] f = new int[n + 1][K];
		for (int i = 0; i < K; i++) {
			f[0][i] = 0;
		}

		int i, j, e;
		for (i = 1; i <= n; i++) {
			for (j = 0; j < K; j++) {
				f[i][j] = Integer.MAX_VALUE;
				for (e = 0; e < K; e++) {
					if (j != e) {
						f[i][j] = Math.min(f[i][j], f[i - 1][e] + costs[i - 1][j]);
					}
				}
			}
		}

		int res = Integer.MAX_VALUE;
		for (i = 0; i < K; i++) {
			res = Math.min(res, f[n][i]);
		}
		return res;
	}

	public static int minCostII03(int[][] costs) {
		int N = costs.length;
		if (N == 0) {
			return 0;
		}

		int K = costs[0].length;
		int INF = Integer.MAX_VALUE;

		int[][] dp = new int[N][K];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < K; j++) {
				dp[i][j] = INF;
			}
		}

		for (int j = 0; j < K; j++) {
			dp[0][j] = costs[0][j];
		}

		for (int i = 1; i < N; i++) {
			for (int j = 0; j < K; j++) {
				for (int k = 0; k < K; k++) {
					if (j == k) {
						continue;
					}
					dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + costs[i][j]);
				}
			}
		}
		int ans = INF;
		for (int j = 0; j < K; j++) {
			ans = Math.min(ans, dp[N - 1][j]);
		}
		return ans;
	}

//作者：acw_weian
//链接：https://leetcode-cn.com/problems/paint-house-ii/solution/acw-dong-tai-gui-hua-java-by-acw_weian/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	public static void main(String[] args) {
		int[][] costs = { { 1, 5, 3 }, { 2, 9, 4 } };
		System.out.println(minCostII03(costs));
	}
}
